package day;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;

/**
 * 502. IPO
 */
public class P502 {
    public int findMaximizedCapital(int k, int w, int[] profits, int[] capital) {
        int[] result = new int[1];
        bt(k, w, 0, profits, capital, new ArrayList<>(), result);
        return result[0];
    }

    private void bt(int k, int w, int begin, int[] profits, int[] capital, List<Integer> savedList, int[] results) {
        if (k == 0 || begin == profits.length) {
            if (w > results[0]) {
                results[0] = w;
            }
        } else {
            for (int i = 0; i < profits.length; i++) {
                if (!savedList.contains(i)) {
                    if (w >= capital[i]) {
                        // 选
                        savedList.add(i);
                        bt(k - 1, w + profits[i], begin + 1, profits, capital, savedList, results);
                        savedList.remove(savedList.size() - 1);
                    }
                    // 不选
                    bt(k, w, begin + 1, profits, capital, savedList, results);
                }
            }
        }
    }


    private int dp(int k, int w, int[] profits, int[] capital) {
        int len = capital.length;
        List<Integer> results = new ArrayList<>();
        results.add(w);

        List<Integer> savedList = new ArrayList<>();
        int max = w;
        for (int i = 0; i < k; i++) {
            //获取这步的最优选择
            int maxProfit = 0, maxIdx = -1;
            for (int j = 0; j < len; j++) {
                if (!savedList.contains(j) && w >= capital[j]) {
                    if (profits[j] > maxProfit) { //选择当前收益最大的项目
                        maxProfit = profits[j];
                        maxIdx = j;
                    }
                }
            }
            // 保存当前选择
            savedList.add(maxIdx);
            w += maxProfit;
        }
        return w;
    }

    public static void main(String[] args) {
        int k = 3, w = 0;
        int[] profits = new int[]{1, 2, 3};
        int[] capital = new int[]{0, 1, 2};
        int result = new P502().dp(k, w, profits, capital);
        System.out.println(result);
    }
}
